/*
* @(#) Sort.java 2018年03月07日
*
* Copyright 2010 NetEase.com, Inc. All rights reserved.
*/
package com.leo.m1803.d07;

import java.util.Arrays;

/**
 *
 * @author xuexiaolei
 * @version 2018年03月07日
 */
public class Sort {
    //***************快排********************
    public static void quickSort(int[] a){
        doQuickSort(a, 0, a.length-1);
    }
    private static void doQuickSort(int[] a, int start, int end){
        if (start < end){
            int pos = partition(a, start, end);
            doQuickSort(a, start, pos-1);
            doQuickSort(a, pos+1, end);
        }
    }
    private static int partition(int[] a, int start, int end){
        int temp = a[start];
        while (start < end){
            while (start < end && a[end]>=temp){ end--; }
            a[start] = a[end];
            while (start < end && a[start]<=temp){ start++; }
            a[end] = a[start];
        }
        a[end] = temp;
        return end;
    }

    //***************堆排********************
    public static void heapSort(int[] a){
        for (int i = a.length/2; i >=0 ; i--) { heapAdjust(a, a.length-1, i); }
        int end = a.length - 1;
        while (end > 0){
            swap(a, 0, end);
            heapAdjust(a, --end, 0);
        }
    }
    private static void heapAdjust(int[] a, int end, int target){
        int child = target*2+1;
        if (child <= end && a[child]>a[target]){
            if (child+1 <=end && a[child+1]>a[child]){ child++; }
            swap(a, target, child);
            heapAdjust(a, end, child);
        }
    }

    //**************直接插入排序********************
    public static void simpleInsertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int temp = i;
            while (temp>0 && a[temp] < a[temp-1]){
                swap(a, temp, temp-1);
                temp--;
            }
        }
    }

    private static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    //**************选择排序********************
    public static void chooseSort(int[] a){
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i+1; j < a.length; j++) {
                if (a[j] < a[min]){ min = j; }
            }
            swap(a, i, min);
        }
    }
    //**************冒泡排序********************
    public static void bullubSort(int[] a){
        for (int i = a.length-1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j+1]){ swap(a, j, j+1); }
            }
        }
    }
    //**************希尔排序********************
    public static void shellSort(int[] a){
        int gap = a.length>>1;
        while (gap > 0){
            for (int i = 0; i < gap; i++) {
                int cur = i;
                while (cur<a.length){
                    if ((cur+gap)<a.length && a[cur]>a[cur+gap]){
                        swap(a, cur, cur+gap);
                        if (cur-gap > 0) {cur-=gap;}
                    }else {
                        cur+=gap;
                    }
                }
            }
            gap >>=1;
        }
    }
    //**************归并排序********************
    public static void mergeSort(int[] a){
        doMergeSort(a, 0, a.length-1);
    }
    private static void doMergeSort(int[] a, int start, int end){
        if (start < end){
            int mid = (end+start)/2;
            doMergeSort(a, start, mid);
            doMergeSort(a, mid+1, end);
            merge(a, start , mid, end);
        }
    }

    private static void merge(int[] a, int start, int mid, int end) {
        int[] temp = new int[end-start+1];
        int i = start, j = mid+1, k = 0;
        while (i<=mid && j <= end){
            if (a[i] < a[j]){
                temp[k++] = a[i++];
            }else {
                temp[k++] = a[j++];
            }
        }
        while (i<=mid){ temp[k++] = a[i++]; }
        while (j<=end){ temp[k++] = a[j++]; }
        for (int l = 0; l < temp.length; l++) {
            a[l+start] = temp[l];
        }
    }
    //**************基数排序********************

    public static void main(String[] args) {
        int[] a = {5,2,4,7,2,34,8,25,234,53,123,42,143,13,1,4,613,4612,3,42,52,4,3,9,9,9,9,9};
//        quickSort(a);
//        heapSort(a);
//        simpleInsertSort(a);
//        chooseSort(a);
//        bullubSort(a);
//        shellSort(a);
        mergeSort(a);
        System.out.println(Arrays.toString(a));

    }
}
